#include"tree.h"
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
CBTType* InitTree()
{
	CBTType* node;
	
	if (node = (CBTType*)malloc(sizeof(CBTType)))
	{
		printf("请先输入一个根节点数据：\n");
		scanf("%s", &node->data);
		node->left = NULL;
		node->right = NULL;
		if (node != NULL)
		{
			return node;
		}
		else
		{
			return NULL;
		}

	}
	return NULL;
}

void AddTreeNode(CBTType* treeNode)
{
	CBTType* pnode, * parent;
	DATA data;
	int menusel;

	if (pnode = (CBTType*)malloc(sizeof(CBTType)))
	{
		printf("输入二叉树结点数据：\n");
		fflush(stdin);
		scanf("%s", &pnode->data);
		pnode->left = NULL;
		pnode->right = NULL;

		printf("输入该结点的父节点数据：\n");
		fflush(stdin);
		scanf("%s", &data);
		parent = TreeFindNode(treeNode, data);//找到指定数据的结点
		if (!parent)
		{
			printf("未找到该父节点！\n");
			free(pnode);
			return;
		}
		printf("1.添加该结点到左子树\n2.添加该结点到右子树\n");
		do
		{
			scanf("%d",&menusel);//字符类型变量
			//menusel -= '0';
			if (menusel == 1 || menusel == 2)
			{
				if (parent == NULL)
				{
					printf("父节点不存在，先设置父节点！\n");
				}
				else
				{
					switch (menusel)
					{
					case 1:
						if (parent->left)
						{
							printf("左子树结点不为空！\n");
						}
						else
						{
							parent->left = pnode;
						}
						break;
					case 2:
					
						if (parent->right)
						{
							printf("右子树结点不为空！\n");
						}
						else
						{
							parent->right = pnode;
						}
						break;
					default:
						printf("无效参数！\n");
						
					}
				}
			}
		} while (menusel != 1 && menusel != 2);
		
	}
}

CBTType* TreeFindNode(CBTType* treeNode, DATA data)
{
	CBTType* ptr;

	if (treeNode == NULL)
	{
		return NULL;
	}
	else
	{
		if (treeNode->data == data)
		{
			return treeNode;
		}
		else
		{
			if (ptr = TreeFindNode(treeNode->left, data))
			{
				return ptr;
			}
			else if (ptr = TreeFindNode(treeNode->right, data))
			{
				return ptr;
			}
			else
			{
				return NULL;
			}
		}
	}
}

CBTType* TreeLeftNode(CBTType* treeNode)
{
	if (treeNode) {
		return treeNode->left;
	}
	else
	{
		return NULL;
	}
}

CBTType* TreeRightNode(CBTType* treeNode)
{

	if (treeNode) {
		return treeNode->right;
	}
	else
	{
		return NULL;
	}
}

int TreeIsEmpty(CBTType* treeNode)
{
	if (treeNode)
	{
		return 0;
	}
	else return 1;
}
int TreeDepth(CBTType* treeNode)
{
	int depleft, depright;

	if (treeNode == NULL)
	{
		return 0;//对于空树，深度为0
	}
	else
	{
		depleft = TreeDepth(treeNode->left);//递归调用
		depright = TreeDepth(treeNode->right);
		if (depleft > depright)
		{
			return depleft + 1;
		}
		else
		{
			return depright + 1;
		}

	}
}

void ClearTree(CBTType* treeNode)//清空二叉树
{
	if (treeNode)
	{
		ClearTree(treeNode->left);//清空左子树（递归调用）
		ClearTree(treeNode->right);//清空右子树
		free(treeNode);//释放结点内存
		treeNode = NULL;

	}
}

void TreeNodeData(CBTType* p)//显示结点数据
{
	printf("%c ", p->data);
}

void LevelTree(CBTType* treeNode, void (*TreeNodeData)(CBTType* p))
{
	CBTType* p;
	CBTType* q[MANLEN]; //定义一个顺序栈
	int head = 0, tail = 0;

	if (treeNode)
	{
		tail = (tail + 1) % MANLEN;//计算循环队列队尾序号
		q[tail] = treeNode;//将二叉树根指针入队
	}
	while (head != tail)
	{
		head = (head + 1) % MANLEN;//计算循环队列队首序号
		p = q[head];//获取队首元素
		TreeNodeData(p);//处理队首元素
		if (p->left != NULL)
		{
			tail = (tail + 1) % MANLEN;
			q[tail] = p->left;
		}
		if (p->right != NULL)
		{
			tail = (tail + 1) % MANLEN;
			q[tail] = p->right;
		}
	}

}

void DLRTree(CBTType* treeNode, void (*TreeNodeData)(CBTType* p))
{
	if (treeNode)
	{
		TreeNodeData(treeNode);
		DLRTree(treeNode->left, TreeNodeData);
		DLRTree(treeNode->right, TreeNodeData);
	}
}

void LDRTree(CBTType* treeNode, void (*TreeNodeData)(CBTType* p))
{
	if (treeNode)
	{
		LDRTree(treeNode->left, TreeNodeData);
		TreeNodeData(treeNode);
		LDRTree(treeNode->right, TreeNodeData);
	}
}

void LRDTree(CBTType* treeNode, void (*TreeNodeData)(CBTType* p))
{
	if (treeNode)
	{
		LRDTree(treeNode->left, TreeNodeData);
		LRDTree(treeNode->right, TreeNodeData);
		TreeNodeData(treeNode);
	}
}


114. 二叉树展开为链表
class Solution {
public:
    void DLRTree(TreeNode* root,vector<TreeNode*>&l){
        if(root!=NULL){
            l.push_back(root);
            DLRTree(root->left,l);
            DLRTree(root->right,l);

        }
    }

    void flatten(TreeNode* root) {
        vector<TreeNode*>l;
        DLRTree(root,l);
        int n=l.size();
        for(int i=1;i<n;i++){
            TreeNode*prev=l.at(i-1),*curr=l.at(i);
            prev->left=nullptr;
            prev->right=curr;
        }
    }
};




